TNotes.leetcode

Appearance

0482. 密钥格式化【简单】

0482. 密钥格式化【简单】 ​

1. 📝 题目描述 ​

给定一个许可密钥字符串 s，仅由字母、数字字符和破折号组成。字符串由 n 个破折号分成 n + 1 组。你也会得到一个整数 k。

我们想要重新格式化字符串 s，使每一组包含 k 个字符，除了第一组，它可以比 k 短，但仍然必须包含至少一个字符。此外，两组之间必须插入破折号，并且应该将所有小写字母转换为大写字母。

返回 重新格式化的许可密钥。

示例 1：

txt
输入：S = "5F3Z-2e-9-w", k = 4
输出："5F3Z-2E9W"
解释：字符串 S 被分成了两个部分，每部分 4 个字符；
     注意，两个额外的破折号需要删掉。

示例 2：

txt
输入：S = "2-5g-3-J", k = 2
输出："2-5G-3J"
解释：字符串 S 被分成了 3 个部分，按照前面的规则描述，第一部分的字符可以少于给定的数量，其余部分皆为 2 个字符。

提示：

  • 1 <= s.length <= 10^5
  • s 只包含字母、数字和破折号 '-'.
  • 1 <= k <= 10^4

2. 🎯 s.1 - 暴力解法 - 从左往右 → ​

js
/**
 * @param {string} s
 * @param {number} k
 * @return {string}
 */
var licenseKeyFormatting = function (s, k) {
  // 移除所有破折号并将字母转为大写
  let cleaned = s.replace(/-/g, '').toUpperCase()

  // 如果处理后的字符串为空，返回空字符串
  if (cleaned.length === 0) {
    return ''
  }

  let result = []
  let firstGroupLength = cleaned.length % k

  // 处理第一组（长度可能小于k）
  if (firstGroupLength > 0) {
    result.push(cleaned.substring(0, firstGroupLength))
  }

  // 处理后续每组（每组k个字符）
  for (let i = firstGroupLength; i < cleaned.length; i += k) {
    result.push(cleaned.substring(i, i + k))
  }

  // 用破折号连接各组
  return result.join('-')
}
  • 时间复杂度：O(n)，其中 n 是字符串 s 的长度，需要遍历字符串进行处理
  • 空间复杂度：O(n)，需要额外空间存储处理后的字符串
  • 算法思路：
    1. 字符串预处理：
      • 使用 s.replace(/-/g, '') 移除所有破折号
      • 使用 toUpperCase() 将所有字母转为大写
    2. 计算第一组长度：
      • 使用 cleaned.length % k 计算第一组的长度
      • 如果能整除，第一组长度为 k；否则为余数
    3. 分组处理：
      • 如果第一组长度大于 0，先处理第一组
      • 然后从第一组之后开始，每 k 个字符分为一组
    4. 格式化输出：
      • 使用 join('-') 将各组用破折号连接
  • 执行过程示例
txt
1. 预处理: cleaned = "5F3Z2E9W"
2. cleaned.length = 8, 8 % 4 = 0
3. 第一组长度为 0，直接按每组 4 个字符分组:
   - 第一组: "5F3Z"
   - 第二组: "2E9W"
4. 用破折号连接: "5F3Z-2E9W"
txt
1. 预处理: cleaned = "25G3J"
2. cleaned.length = 5, 5 % 2 = 1
3. 第一组长度为 1: "2"
4. 后续分组:
   - 第二组: "5G"
   - 第三组: "3J"
5. 用破折号连接: "2-5G-3J"

3. 🎯 s.2 - 暴力解法 - 从右往左 ← ​

js
/**
 * @param {string} s
 * @param {number} k
 * @return {string}
 */
var licenseKeyFormatting = function (s, k) {
  // 移除所有破折号并将字母转为大写
  let cleaned = s.replace(/-/g, '').toUpperCase()

  let result = ''

  // 从右向左每k个字符分组
  for (let i = cleaned.length - 1; i >= 0; i--) {
    // 每k个字符添加一个破折号（除了最左边）
    if (result.length % (k + 1) === k) {
      result = '-' + result
    }
    result = cleaned[i] + result
  }

  return result
}
  • 时间复杂度：O(n)，其中 n 是字符串 s 的长度，需要遍历字符串进行处理
  • 空间复杂度：O(n)，需要额外空间存储处理后的字符串

Discussions